﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace IceCS.DataStructure.Helpers
{
    /// <summary>
    /// 排序类，默认排序后结果都是递增排序，可以使用 Reverse 方法倒序
    /// </summary>
    public static class SortHelper
    {
        /// <summary>
        /// 插入排序
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static int[] InsertSort(int[] source)
        {
            var result = new int[source.Length];
            for (int i = 1; i < source.Length; i++)
            {
                if (source[i] < source[i - 1])
                {
                    int temp = source[i];
                    int j = 0;
                    for (j = i - 1; j >= 0 && temp < source[j]; j--)
                    {
                        source[j + 1] = source[j];
                    }
                    source[j + 1] = temp;
                }
            }
            return result;
        }

        /// <summary>
        /// 希尔排序
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static int[] ShellSort(int[] source)
        {
            var result = new int[source.Length];
            return result;
        }

        /// <summary>
        /// 快速排序
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static int[] FastSort(int[] source)
        {
            var result = new int[source.Length];
            return result;
        }

        public static int[] Reverse(int[] source)
        {
            var result = new int[source.Length];
            for (int i = source.Length - 1; i > 0; i--)
            {
                var idx = source.Length - 1;
                result[idx - i] = source[i];
            }
            return result;
        }
    }
}
